package com.yaoli.ajob;

/**
 * dp 算法
 *
 * 将矩阵保存在一个数组中
 *
 * 使用动态规划算法 计算
 *
 * Created by will on 2017/4/16.
 */
public class _304_RangeSumQuery2DImmutable {
    public static void main(String[] args) {
//        int temp [][] = {
//                            {3, 0, 1, 4, 2},
//                            {5, 6, 3, 2, 1},
//                            {1, 2, 0, 1, 5},
//                            {4, 1, 0, 1, 7},
//                            {1, 0, 3, 0, 5}
//                        };
        int temp [][] = {{}};
        _304_RangeSumQuery2DImmutable rangeSumQuery2DImmutable = new _304_RangeSumQuery2DImmutable(temp);
        int res = rangeSumQuery2DImmutable.sumRegion(1, 1, 2, 2);
        System.out.println(res);
    }
    int dp[][];

    public _304_RangeSumQuery2DImmutable(int[][] matrix) {

        if(matrix == null || matrix.length == 0 || matrix[0].length == 0){
            dp =new int [0][0];
            return ;
        }
        dp = new int[matrix.length + 1][matrix[0].length + 1];

        for(int i = 1 ; i <= matrix.length ; i++){
            for(int j = 1; j <= matrix[0].length ; j++){
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - 1] + matrix[i - 1][j - 1];
            }
        }

        for(int i = 0 ; i < dp.length ; i++){
            for (int j = 0; j < dp[0].length; j++) {
                System.out.print(dp[i][j]+"\t");
            }
            System.out.println("");
        }
    }

    public int sumRegion(int row1, int col1, int row2, int col2) {
        int maxrow = Math.max(row1,row2);
        int minrow = Math.min(row1,row2);

        int maxcol = Math.max(col1,col2);
        int mincol = Math.min(col1,col2);

        int result = dp[maxrow + 1][maxcol + 1] - dp[maxrow + 1][mincol] - dp[minrow][maxcol + 1] + dp[minrow][mincol];

        return result;
    }
}
